# -*- coding: utf-8 -*-

from random import uniform
from time import clock
from bubble_sort import bubblesortClass
from insertion_sort import insertionsortClass
from heapsort import HeapsortAlgorithm
from merge_sort import MergesortAlgorithm
from quicksort import quicksortAlgorithm


#Z = [1] + range(500, 10500, 500)
Z = [1] + range(50, 1050, 50)
#print Z
#Z = [16,4,10,14,7,9,3,2,1,8]
T = []
M = 25
#bubble = bubblesortClass()
#heaps = HeapsortAlgorithm()
#ins = insertionsortClass()
merg = MergesortAlgorithm()
#quick = quicksortAlgorithm()
for n in Z:
    A = [ uniform(0.0,1.0) for k in xrange(n)]
    #A = [ k for k in xrange(n)]
    #print A
    #print
    tempos = []
    for k in range(M):
        #print k
        t1 = clock()
        #bubble.bubbleSort(A)
        #heaps.heapsort(A)
        #ins.insertionSort(A)
        merg.merge_sort(A,1,len(A))
        #quick.quicksort(A, 0, (len(A)-1))
        t2 = clock()
        tempos.append(t2-t1)
        #print t2-t1

    media = reduce(lambda x, y: x + y, tempos) / len(tempos)
    var = reduce(lambda x, y: x + (y-media)**2, [0] + tempos) / len(tempos)
    
    T.append((n,media, var))

X = [n for n, media, var in T]
Y = [media for n, media, var in T]
ct=15e6
Z = [n**2/ct for n, media, var in T]

import matplotlib.pyplot as plt
plt.grid(True)
plt.ylabel(u'T(n) - tempo de execução médio em segundos')
plt.xlabel(u'n - número de elementos')
plt.plot(X,Y,'rs', label="resultado experimental")
plt.plot(X, Z, 'b^', label=u"previsão teórica")
plt.legend()
plt.show()
            
